Modern applications such as computer games may use image synthesis to take a small sample image and create a larger image, e.g. for use in representing a background or a texture of a surface in an image. Image synthesis can also be used in other situations, such as for post-production of films. The images may for example be textures. A block of a texture to be applied to a surface in a scene (e.g. patterned material or brickwork, etc.) can be stored for use in rendering images which include surfaces having that texture. The block of texture may be small (e.g. a 64×64 block of pixels) to thereby reduce the amount of storage used to store the texture. However, the texture may be applied to surfaces in a scene which are larger than the block in which case the small texture is often simply repeated which can look artificial and unappealing. Instead, texture synthesis can be used to generate a larger block of the texture for use in rendering the scene. Texture synthesis can be performed in many different ways, and one aim of texture synthesis is to create a texture which appears non-repetitive, i.e. which does not appear to be made up of repeated blocks.
Some existing algorithms for texture synthesis can generate results with a good visual effect, but the storage requirements and rendering performance needed to perform these texture synthesis algorithms are large, and in particular are too large to be performed in real-time on low cost devices and mobile devices which typically have limited processing resources and/or storage capacity. Some other existing algorithms aim to achieve real-time performance of texture synthesis, but their results are typically not satisfactory in terms of including visual artefacts and/or obvious repeating blocks.
There are a number of existing texture synthesis techniques which can be generally classified into three kinds: (i) parametric models, (ii) exemplar analysis, and (iii) patch matching. The parametric models may be good for image analysis but often perform unevenly for a rich variety of textures. The exemplar analysis techniques guide the texture synthesis by analysis of exemplars from a sample image rather than using a fixed number of parameters. These exemplar analysis techniques can perform well for a majority of textures, but produce only a pixel at a time, i.e. a pixel per iteration, so they are slow and typically not suitable for real-time rendering of large images (e.g. including thousands or millions of pixels). Patch matching methods take patches from the sample image and stitch them together into an output texture. Instead of one pixel at a time, patch matching methods manage to create acceptable results from fragments of a sample image. All three kinds of texture synthesis methods mentioned above take a long time, e.g. minutes or even hours, to generate a large texture, making them unsuitable for use in real-time rendering, e.g. for use in rendering images for games and other applications with which a user interacts.
A paper entitled “Wang tiles for image and texture generation” by Cohen M. F., Shade J., Hiller S. and Deussen O., Vol. 22, ACM, 2003, describes a technique to create non-periodic textures at run time, by pre-producing a small set of Wang Tiles using content of a sample image. Wang Tiles can be generated off-line and with them, a relatively simple stochastic algorithm is used to tile the output texture. Thus real-time performance can be achieved even for large images.
Methods based on Wang Tiles tend to outperform other existing texture synthesis algorithms in terms of having higher running speed, lower memory cost and lower bandwidth usage. However, there are limitations with methods based on Wang Tiles. For example, it can be difficult to create enough tiles from a small sample image to avoid the inclusion of repeating of patterns in a synthesised image. Furthermore, diamond shaped artefacts, which accompany the generation of Wang Tiles are often apparent. Also, optimizations to generate sufficient numbers of Wang Tiles for synthesising a large image may be time consuming.
FIG. 1 shows an example of an input image 102 and a synthesised image 104 which is determined using a method based on Wang Tiles. Diamond shaped artefacts are apparent in the synthesised image 104. “Artefacts” are undesired visual effects which are not present in the input image 102, but which are present in the synthesised image 104, and result from the method used to generate the synthesised image.
A texture synthesis method which could generate arbitrarily large textures in real-time on devices which have limited processing and/or storage resources, without creating unsatisfactory artefacts or repeating patterns in synthesised textures, would be useful.